package nowcoder

/*描述
给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

数据范围： n ≤ 1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。*/

func ReverseList(pHead *ListNode) *ListNode {
	// write code here
	if pHead == nil {
		return nil
	}
	next := pHead.Next
	pHead.Next = nil
	lastNode := pHead
	for next != nil {
		nextNode := next.Next
		next.Next = lastNode
		lastNode = next
		next = nextNode
		if next == nil {
			return lastNode
		}
	}
	return pHead
}
